{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Robot Collisions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #sorting #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #排序 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: survivedRobotsHealths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #机器人碰撞"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有 <code>n</code> 个机器人，编号从 <strong>1</strong> 开始，每个机器人包含在路线上的位置、健康度和移动方向。</p>\n",
    "\n",
    "<p>给你下标从 <strong>0</strong> 开始的两个整数数组 <code>positions</code>、<code>healths</code> 和一个字符串 <code>directions</code>（<code>directions[i]</code> 为 <strong>'L'</strong> 表示 <strong>向左</strong> 或 <strong>'R'</strong> 表示 <strong>向右</strong>）。 <code>positions</code> 中的所有整数 <strong>互不相同</strong> 。</p>\n",
    "\n",
    "<p>所有机器人以 <strong>相同速度</strong> <strong>同时</strong> 沿给定方向在路线上移动。如果两个机器人移动到相同位置，则会发生 <strong>碰撞</strong> 。</p>\n",
    "\n",
    "<p>如果两个机器人发生碰撞，则将 <strong>健康度较低</strong> 的机器人从路线中 <strong>移除</strong> ，并且另一个机器人的健康度 <strong>减少 1</strong> 。幸存下来的机器人将会继续沿着与之前 <strong>相同</strong> 的方向前进。如果两个机器人的健康度相同，则将二者都从路线中移除。</p>\n",
    "\n",
    "<p>请你确定全部碰撞后幸存下的所有机器人的 <strong>健康度</strong> ，并按照原来机器人编号的顺序排列。即机器人 1 （如果幸存）的最终健康度，机器人 2 （如果幸存）的最终健康度等。 如果不存在幸存的机器人，则返回空数组。</p>\n",
    "\n",
    "<p>在不再发生任何碰撞后，请你以数组形式，返回所有剩余机器人的健康度（按机器人输入中的编号顺序）。</p>\n",
    "\n",
    "<p><strong>注意：</strong>位置&nbsp; <code>positions</code> 可能是乱序的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img height=\"169\" src=\"https://assets.leetcode.com/uploads/2023/05/15/image-20230516011718-12.png\" width=\"808\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = \"RRRRR\"\n",
    "<strong>输出：</strong>[2,17,9,15,10]\n",
    "<strong>解释：</strong>在本例中不存在碰撞，因为所有机器人向同一方向移动。所以，从第一个机器人开始依序返回健康度，[2, 17, 9, 15, 10] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img height=\"176\" src=\"https://assets.leetcode.com/uploads/2023/05/15/image-20230516004433-7.png\" width=\"717\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>positions = [3,5,2,6], healths = [10,10,15,12], directions = \"RLRL\"\n",
    "<strong>输出：</strong>[14]\n",
    "<strong>解释：</strong>本例中发生 2 次碰撞。首先，机器人 1 和机器人 2 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。接下来，机器人 3 和机器人 4 将会发生碰撞，由于机器人 4 的健康度更小，则它会被移除，而机器人 3 的健康度变为 15 - 1 = 14 。仅剩机器人 3 ，所以返回 [14] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img height=\"172\" src=\"https://assets.leetcode.com/uploads/2023/05/15/image-20230516005114-9.png\" width=\"732\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>positions = [1,2,5,6], healths = [10,10,11,11], directions = \"RLRL\"\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>机器人 1 和机器人 2 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。机器人 3 和机器人 4 将会碰撞，因为二者健康度相同，二者都将被从路线中移除。所以返回空数组 [] 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= positions.length == healths.length == directions.length == n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= positions[i], healths[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>directions[i] == 'L'</code> 或 <code>directions[i] == 'R'</code></li>\n",
    "\t<li><code>positions</code> 中的所有值互不相同</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [robot-collisions](https://leetcode.cn/problems/robot-collisions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [robot-collisions](https://leetcode.cn/problems/robot-collisions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,3,2,1]\\n[2,17,9,15,10]\\n\"RRRRR\"', '[3,5,2,6]\\n[10,10,15,12]\\n\"RLRL\"', '[1,2,5,6]\\n[10,10,11,11]\\n\"RLRL\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(positions)\n",
    "        \n",
    "        for i in sorted(range(n), key=lambda x: positions[x]):\n",
    "            p = positions[i]\n",
    "            h = healths[i]\n",
    "            d = directions[i]\n",
    "            \n",
    "            if d == 'L':\n",
    "                while stack and healths[i]:\n",
    "                    j = stack.pop()\n",
    "                    if healths[j] == healths[i]:\n",
    "                        healths[i] = 0\n",
    "                        healths[j] = 0\n",
    "                        break\n",
    "                    elif healths[i] > healths[j]:\n",
    "                        healths[i] -= 1\n",
    "                        healths[j] = 0\n",
    "                    else:\n",
    "                        healths[i] = 0\n",
    "                        healths[j] -= 1\n",
    "                        if healths[j]: stack.append(j)\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        \n",
    "        return [x for x in healths if x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        \n",
    "        \n",
    "        n = len(positions)\n",
    "        index = list(range(n))\n",
    "        index.sort(key=lambda i: positions[i])\n",
    "        left = []\n",
    "        right = []\n",
    "        for idx in index:\n",
    "            d = directions[idx]\n",
    "            if d == 'R':\n",
    "                right.append(idx)\n",
    "                continue\n",
    "            while right:\n",
    "                ri = right[-1]\n",
    "                if healths[ri] > healths[idx]:\n",
    "                    healths[ri] -= 1\n",
    "                    healths[idx] = 1 << 30\n",
    "                    break\n",
    "                right.pop()\n",
    "                if healths[ri] == healths[idx]:\n",
    "                    healths[idx] = 1 << 30\n",
    "                    healths[ri] = 1 << 30\n",
    "                    break\n",
    "                healths[idx] -= 1\n",
    "                healths[ri] = 1 << 30\n",
    "        return [x for x in healths if x != 1 << 30]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        \n",
    "        \n",
    "        n = len(positions)\n",
    "        index = list(range(n))\n",
    "        index.sort(key=lambda i: positions[i])\n",
    "        left = []\n",
    "        right = []\n",
    "        for idx in index:\n",
    "            d = directions[idx]\n",
    "            if d == 'R':\n",
    "                right.append(idx)\n",
    "                continue\n",
    "            while right:\n",
    "                ri = right[-1]\n",
    "                if healths[ri] > healths[idx]:\n",
    "                    healths[ri] -= 1\n",
    "                    healths[idx] = 1 << 30\n",
    "                    break\n",
    "                right.pop()\n",
    "                if healths[ri] == healths[idx]:\n",
    "                    healths[idx] = 1 << 30\n",
    "                    healths[ri] = 1 << 30\n",
    "                    break\n",
    "                healths[idx] -= 1\n",
    "                healths[ri] = 1 << 30\n",
    "        return [x for x in healths if x != 1 << 30]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        ids = sorted(range(n), key=lambda i: positions[i])\n",
    "\n",
    "        fwd = []\n",
    "        for i in ids:\n",
    "            if directions[i] == 'L':\n",
    "                while fwd and healths[i] > 0:\n",
    "                    if healths[fwd[-1]] > healths[i]:\n",
    "                        healths[fwd[-1]] -= 1\n",
    "                        healths[i] = 0\n",
    "                    elif healths[fwd[-1]] < healths[i]:\n",
    "                        healths[i] -= 1\n",
    "                        healths[fwd[-1]] = 0\n",
    "                        fwd.pop()\n",
    "                    else:\n",
    "                        healths[i] = 0\n",
    "                        healths[fwd[-1]] = 0\n",
    "                        fwd.pop()\n",
    "            else:\n",
    "                fwd.append(i)\n",
    "\n",
    "        return [v for v in healths if v > 0]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "\n",
    "        n = len(positions)\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda it: positions[it])\n",
    "        stack = []\n",
    "        for i in ind:\n",
    "            if directions[i] == \"L\":\n",
    "                while stack:\n",
    "                    if healths[stack[-1]] < healths[i]:\n",
    "                        healths[stack.pop()] = 0\n",
    "                        healths[i] -= 1\n",
    "                    elif healths[stack[-1]] > healths[i]:\n",
    "                        healths[stack[-1]] -= 1\n",
    "                        healths[i] = 0\n",
    "                        break\n",
    "                    else:\n",
    "                        healths[stack.pop()] = 0\n",
    "                        healths[i] = 0\n",
    "                        break\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        return [h for h in healths if h]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        ix = []\n",
    "        n = len(positions)\n",
    "        ss = sorted(range(n),key=lambda x:positions[x])\n",
    "        for x in ss: \n",
    "            if directions[x] == \"R\":\n",
    "                ix.append(x)\n",
    "                continue\n",
    "            while ix and healths[x] > healths[ix[-1]]:\n",
    "                healths[ix[-1]] = 0\n",
    "                healths[x] -= 1\n",
    "                ix.pop()\n",
    "            if ix and healths[x] == healths[ix[-1]]:\n",
    "                healths[x] = 0\n",
    "                healths[ix[-1]] = 0\n",
    "                ix.pop()\n",
    "            elif ix and healths[x] < healths[ix[-1]]:\n",
    "                healths[ix[-1]] -= 1\n",
    "                healths[x] = 0\n",
    "        return [x for x in healths if x]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        \n",
    "        \n",
    "        n = len(positions)\n",
    "        index = list(range(n))\n",
    "        index.sort(key=lambda i: positions[i])\n",
    "        left = []\n",
    "        right = []\n",
    "        for idx in index:\n",
    "            d = directions[idx]\n",
    "            if d == 'R':\n",
    "                right.append(idx)\n",
    "                continue\n",
    "            while right:\n",
    "                ri = right[-1]\n",
    "                if healths[ri] > healths[idx]:\n",
    "                    healths[ri] -= 1\n",
    "                    healths[idx] = 1 << 30\n",
    "                    break\n",
    "                right.pop()\n",
    "                if healths[ri] == healths[idx]:\n",
    "                    healths[idx] = 1 << 30\n",
    "                    healths[ri] = 1 << 30\n",
    "                    break\n",
    "                else:\n",
    "                    healths[idx] -= 1\n",
    "                    healths[ri] = 1 << 30\n",
    "        return [x for x in healths if x != 1 << 30]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        \n",
    "        \n",
    "        n = len(positions)\n",
    "        index = list(range(n))\n",
    "        index.sort(key=lambda i: positions[i])\n",
    "        left = []\n",
    "        right = []\n",
    "        for idx in index:\n",
    "            d = directions[idx]\n",
    "            if d == 'R':\n",
    "                right.append(idx)\n",
    "                continue\n",
    "            while right:\n",
    "                ri = right[-1]\n",
    "                if healths[ri] > healths[idx]:\n",
    "                    healths[ri] -= 1\n",
    "                    healths[idx] = 1 << 30\n",
    "                    break\n",
    "                right.pop()\n",
    "                if healths[ri] == healths[idx]:\n",
    "                    healths[idx] = 1 << 30\n",
    "                    healths[ri] = 1 << 30\n",
    "                    break\n",
    "                else:\n",
    "                    healths[idx] -= 1\n",
    "                    healths[ri] = 1 << 30\n",
    "        return [x for x in healths if x != 1 << 30]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        \n",
    "        \n",
    "        n = len(positions)\n",
    "        index = list(range(n))\n",
    "        index.sort(key=lambda i: positions[i])\n",
    "        left = []\n",
    "        right = []\n",
    "        for idx in index:\n",
    "            d = directions[idx]\n",
    "            if d == 'R':\n",
    "                right.append(idx)\n",
    "                continue\n",
    "            while right:\n",
    "                ri = right[-1]\n",
    "                if healths[ri] < healths[idx]:\n",
    "                    healths[idx] -= 1\n",
    "                    right.pop()\n",
    "                    healths[ri] = 1 << 30\n",
    "                elif healths[ri] > healths[idx]:\n",
    "                    healths[ri] -= 1\n",
    "                    healths[idx] = 1 << 30\n",
    "                    break\n",
    "                else:\n",
    "                    healths[idx] = 1 << 30\n",
    "                    healths[ri] = 1 << 30\n",
    "                    right.pop()\n",
    "                    break\n",
    "        return [x for x in healths if x != 1 << 30]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        w = [_ for _ in range(n)]\n",
    "        w.sort(key=lambda x: positions[x])\n",
    "        ans = [0]*n\n",
    "        stack = []\n",
    "        pos = 0\n",
    "        if directions[w[pos]] == 'L':\n",
    "            ans[w[pos]] = healths[w[pos]]\n",
    "        else:\n",
    "            stack.append(w[pos])\n",
    "        while pos < n:\n",
    "            if pos+1 < n:\n",
    "                if directions[w[pos+1]] == 'R':\n",
    "                    stack.append(w[pos+1])\n",
    "                else:\n",
    "                    if stack:\n",
    "                        idx1 = w[pos+1]\n",
    "                        idx2 = stack.pop()\n",
    "                        while stack and healths[idx1] > healths[idx2]:\n",
    "                            healths[idx1] -= 1\n",
    "                            idx2 = stack.pop()\n",
    "                        if healths[idx1] < healths[idx2]:\n",
    "                            healths[idx2] -= 1\n",
    "                            if healths[idx2] > 0:\n",
    "                                stack.append(idx2)\n",
    "                        elif healths[idx1] > healths[idx2]:\n",
    "                            ans[idx1] = healths[idx1]-1\n",
    "                    else:\n",
    "                        ans[w[pos+1]] = healths[w[pos+1]]\n",
    "            pos += 1\n",
    "        while stack:\n",
    "            idx = stack.pop()\n",
    "            ans[idx] = healths[idx]\n",
    "        h = []\n",
    "        for v in ans:\n",
    "            if v:\n",
    "                h.append(v)\n",
    "        return h\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        st = []\n",
    "        n = len(positions)\n",
    "        ans = [0] * n\n",
    "        idxs = sorted(range(n), key=lambda x:positions[x])\n",
    "        for idx in idxs:\n",
    "            if(directions[idx]=='L'):\n",
    "                if(not st):\n",
    "                    ans[idx] = healths[idx]\n",
    "                else:\n",
    "                    st_health = healths[st[-1]]\n",
    "                    cur_health = healths[idx]\n",
    "                    while(st and cur_health!=0):\n",
    "                        if(st_health == cur_health):\n",
    "                            st.pop()\n",
    "                            cur_health = 0\n",
    "                        elif(st_health > cur_health):\n",
    "                            cur_health = 0\n",
    "                            healths[st[-1]]-=1\n",
    "                        else:\n",
    "                            st.pop()\n",
    "                            if(st):\n",
    "                                st_health = healths[st[-1]]\n",
    "                            cur_health-=1\n",
    "                    if(cur_health > 0):\n",
    "                        ans[idx] = cur_health\n",
    "            else:\n",
    "                st.append(idx)\n",
    "        while(st):\n",
    "            idx = st.pop()\n",
    "            ans[idx] = healths[idx]\n",
    "        return [item for item in ans if item != 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        idxs = sorted(zip(positions, range(n)))\n",
    "        q = []\n",
    "        for _, p in idxs:\n",
    "            if directions[p] == 'L':\n",
    "                while q and directions[q[-1]] == 'R':\n",
    "                    if healths[q[-1]] < healths[p]:\n",
    "                        healths[q[-1]] = 0\n",
    "                        healths[p] -= 1\n",
    "                        q.pop()\n",
    "                    elif healths[q[-1]] == healths[p]:\n",
    "                        healths[q[-1]] = 0\n",
    "                        healths[p] = 0\n",
    "                        q.pop()\n",
    "                        break\n",
    "                    else:\n",
    "                        healths[q[-1]] -= 1\n",
    "                        healths[p] = 0\n",
    "                        break\n",
    "            else:\n",
    "                q.append(p)\n",
    "                \n",
    "        return list(filter(None, healths))\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        robots = list(range(len(positions)))\n",
    "        robots.sort(key=lambda x: positions[x])\n",
    "        p = []\n",
    "        for r in robots:\n",
    "            if len(p) == 0 or directions[r] == 'R' or p[-1][2] == 'L':\n",
    "                p.append((r, healths[r], directions[r]))\n",
    "            else:\n",
    "                cur = healths[r]\n",
    "                completed = False\n",
    "                while len(p) > 0 and p[-1][2] == 'R':\n",
    "                    a = p.pop()\n",
    "                    if a[1] == cur:\n",
    "                        completed = True\n",
    "                        break\n",
    "                    elif a[1] > cur:\n",
    "                        p.append((a[0], a[1]-1, 'R'))\n",
    "                        completed = True\n",
    "                        break\n",
    "                    else:\n",
    "                        cur -= 1\n",
    "                if not completed and cur > 0:\n",
    "                    p.append((r, cur, 'L'))              \n",
    "        p.sort(key=lambda x: x[0])\n",
    "        return [x[1] for x in p]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        stack = []\n",
    "        for i,pos in sorted(enumerate(positions), key = lambda x : x[1]):\n",
    "            need_drop = False\n",
    "            while stack and directions[i] == \"L\" and directions[stack[-1]] == \"R\":\n",
    "                if healths[i] == healths[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                    need_drop = True\n",
    "                    break\n",
    "                elif healths[i] > healths[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                    healths[i] -= 1\n",
    "                else:\n",
    "                    need_drop = True\n",
    "                    healths[stack[-1]] -= 1\n",
    "                    break\n",
    "            if not need_drop:\n",
    "                stack.append(i)\n",
    "        stack.sort()\n",
    "        return [healths[i] for i in stack]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        a = [i for i in range(n)]\n",
    "        a.sort(key=lambda x: positions[x])\n",
    "        res = []\n",
    "        stack = []\n",
    "        for i in a:\n",
    "            h = healths[i]\n",
    "            if directions[i] == 'L':\n",
    "                while stack:\n",
    "                    if stack[-1][1] < h:\n",
    "                        h -= 1\n",
    "                        stack.pop()\n",
    "                    elif stack[-1][1] > h:\n",
    "                        h = 0\n",
    "                        stack[-1][1] -= 1\n",
    "                        break\n",
    "                    else:\n",
    "                        h = 0\n",
    "                        stack.pop()\n",
    "                        break\n",
    "                if h > 0:\n",
    "                    res.append([i, h])\n",
    "            else:\n",
    "                stack.append([i, h])\n",
    "        res.extend(stack)\n",
    "        res.sort()\n",
    "        return [p for _, p in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        idx = list(range(n))\n",
    "        st = []\n",
    "        for i, pos, d in sorted(zip(idx, positions, directions), key=lambda x: x[1]):\n",
    "            if d == 'R':\n",
    "                st.append(i)\n",
    "                continue\n",
    "            \n",
    "            # 用栈中的机器人和当前机器人碰撞\n",
    "            while st and directions[st[-1]] == 'R' and healths[i] > 0:\n",
    "                if healths[st[-1]] > healths[i]:\n",
    "                    healths[st[-1]] -= 1\n",
    "                    healths[i] = 0\n",
    "                elif healths[st[-1]] < healths[i]:\n",
    "                    st.pop()\n",
    "                    healths[i] -= 1\n",
    "                else:\n",
    "                    st.pop()\n",
    "                    healths[i] = 0\n",
    "            if healths[i] > 0:\n",
    "                st.append(i)\n",
    "        st.sort()\n",
    "        ans = []\n",
    "        for i in st:\n",
    "            ans.append(healths[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        rightStack = []\n",
    "        leftStack = []\n",
    "        n = len(positions)\n",
    "        pI = [i for i in range(n)]\n",
    "        pI.sort(key = lambda x: positions[x])\n",
    "        for i in pI:\n",
    "            hi, di = healths[i], directions[i]\n",
    "            if di == 'R':\n",
    "                rightStack.append([hi, i])\n",
    "            else:\n",
    "                while rightStack and rightStack[-1][0] < hi:\n",
    "                    rightStack.pop()\n",
    "                    hi-=1\n",
    "                if rightStack:\n",
    "                    if rightStack[-1][0] == hi:\n",
    "                        rightStack.pop()\n",
    "                    else:\n",
    "                        rightStack[-1][0] = rightStack[-1][0]-1\n",
    "                else:\n",
    "                    leftStack.append([hi, i])\n",
    "        ret = leftStack + rightStack\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "        ans = [x[0] for x in ret]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, p: List[int], h: List[int], d: str) -> List[int]:\n",
    "        n=len(p)\n",
    "        from sortedcontainers import SortedList\n",
    "        l,r=[],SortedList()\n",
    "        for i in range(n):\n",
    "            if d[i]=='R':\n",
    "                l.append([p[i],i])\n",
    "            else:\n",
    "                r.add([p[i],i])\n",
    "        l.sort()\n",
    "        while l:\n",
    "            j=bisect_left(r,l[-1])\n",
    "            if j==len(r):\n",
    "                l.pop()\n",
    "                continue\n",
    "            x,y=r[j]\n",
    "            if h[y]<h[l[-1][1]]:\n",
    "                h[y]=0\n",
    "                r.pop(j)\n",
    "                h[l[-1][1]]-=1\n",
    "                if h[l[-1][1]]==0:\n",
    "                    l.pop()\n",
    "            elif h[y]>h[l[-1][1]]:\n",
    "                h[l[-1][1]]=0\n",
    "                l.pop()\n",
    "                h[y]-=1\n",
    "                if h[y]==0:\n",
    "                    r.pop(j)\n",
    "            else:\n",
    "                h[l[-1][1]]=0\n",
    "                h[y]=0\n",
    "                l.pop()\n",
    "                r.pop(j)\n",
    "        return [h[i] for i in range(n) if h[i]>0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        robots=[]\n",
    "        n=len(directions)\n",
    "        for i in range(n):\n",
    "            robots.append([positions[i], healths[i], directions[i], i])\n",
    "        robots.sort(key=lambda x:x[0])\n",
    "        st=[]\n",
    "        for _ in robots:\n",
    "            if _[2]=='L':\n",
    "                temp=_\n",
    "                while st and temp[1]>0 and st[-1][2]=='R':\n",
    "                    if temp[1]<st[-1][1]:\n",
    "                        st[-1][1]-=1\n",
    "                        temp[1]=0\n",
    "                    elif temp[1]>st[-1][1]:\n",
    "                        temp[1]-=1\n",
    "                        st.pop(-1)\n",
    "                    elif temp[1]==st[-1][1]:\n",
    "                        temp[1]=0\n",
    "                        st.pop(-1)\n",
    "                if temp[1]>0:\n",
    "                    st.append(temp)\n",
    "            else:\n",
    "                st.append(_)\n",
    "        res=list(filter(lambda x:x[1]>0, st))\n",
    "        res.sort(key=lambda x:x[3])\n",
    "        return [x[1] for x in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        message = []\n",
    "        ii = range(len(positions))\n",
    "        for pst, hlt, drt, i in zip(positions, healths, directions, ii):\n",
    "            message.append([pst, hlt, drt, i])\n",
    "        message.sort(key=lambda x:x[0])\n",
    "        lenm = len(message)\n",
    "        s = []\n",
    "        for i in range(lenm):\n",
    "            mes = message[i]\n",
    "            if not s:\n",
    "                s.append(mes)\n",
    "            elif mes[2] == \"R\":\n",
    "                s.append(mes)\n",
    "            elif mes[2] == \"L\":\n",
    "                while s and s[-1][2] == \"R\" and mes[1] != 0:\n",
    "                    if s[-1][1] > mes[1]:\n",
    "                        s[-1][1] -= 1\n",
    "                        mes[1] = 0\n",
    "                    elif s[-1][1] < mes[1]:\n",
    "                        s.pop()\n",
    "                        mes[1] -= 1\n",
    "                    else:\n",
    "                        s.pop()\n",
    "                        mes[1] = 0\n",
    "                if mes[1] > 0:\n",
    "                    s.append(mes)\n",
    "        \n",
    "        s.sort(key = lambda x:x[3])\n",
    "        \n",
    "        ans = []\n",
    "        for p in s:\n",
    "            ans.append(p[1])\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        robot_list = []\n",
    "        for i in range(len(positions)):\n",
    "            tmp = [positions[i], healths[i], directions[i], i]\n",
    "            robot_list.append(tmp)\n",
    "        \n",
    "        robot_list.sort(key=lambda x:x[0])\n",
    "        \n",
    "        left = []\n",
    "        add = []\n",
    "        for i in robot_list:\n",
    "            if i[2] == \"R\":\n",
    "                left.append(i)\n",
    "                continue\n",
    "            \n",
    "            while left:\n",
    "                end = left[-1]\n",
    "                if end[1] > i[1]:\n",
    "                    end[1] -= 1\n",
    "                    break\n",
    "                if end[1] == i[1]:\n",
    "                    left.pop()\n",
    "                    break\n",
    "                i[1] -= 1\n",
    "                left.pop()\n",
    "            else:\n",
    "                add.append(i)\n",
    "        robot_leave = left + add\n",
    "        robot_leave.sort(key=lambda x:x[3])\n",
    "        return list(map(lambda x:x[1], robot_leave))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        if n == 1:\n",
    "            return healths\n",
    "        arr = [[positions[i], healths[i], directions[i], i] for i in range(n)]\n",
    "        arr.sort(key=lambda x: x[0])\n",
    "        left = []\n",
    "        right = []\n",
    "        for i in arr:\n",
    "            if i[2] == 'L':\n",
    "                while right and i[1] > right[-1][1]:\n",
    "                    right.pop()\n",
    "                    i[1] -= 1\n",
    "                if i[1] == 0:\n",
    "                    break\n",
    "                elif not right:\n",
    "                    left.append(i)\n",
    "                elif i[1] == right[-1][1]:\n",
    "                    right.pop()\n",
    "                else:\n",
    "                    right[-1][1] -= 1\n",
    "                    if right[-1][1] == 0:\n",
    "                        right.pop()\n",
    "            else:\n",
    "                right.append(i)\n",
    "        return [x[1] for x in sorted(left + right, key=lambda i: i[-1])]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        stack = []\n",
    "        op = [i for i in range(len(directions))]\n",
    "        maped = sorted([[positions[i], healths[i], directions[i], op[i]] for i in range(len(positions))])\n",
    "        n = len(maped)\n",
    "        #print(maped)\n",
    "        for i in range(n):\n",
    "            if len(stack) == 0:\n",
    "                stack.append(maped[i])\n",
    "            else:\n",
    "                if stack[-1][2] == 'L' or (stack[-1][2] == 'R' and maped[i][2] == 'R'):\n",
    "                    stack.append(maped[i])\n",
    "                else:\n",
    "                    while stack and stack[-1][2] == 'R' and stack[-1][1] < maped[i][1]:\n",
    "                        maped[i][1] -= 1\n",
    "                        stack.pop()\n",
    "                    if len(stack) == 0 or stack[-1][2] == 'L':\n",
    "                        stack.append(maped[i])\n",
    "                    elif stack[-1][1] == maped[i][1]:\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        stack[-1][1] -= 1\n",
    "            #print(stack)\n",
    "        stack.sort(key = lambda x: x[3])\n",
    "        return [s[1] for s in stack]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        # 存储机器人的健康值\n",
    "        hs = [0] * n\n",
    "        # 存储向右机器人的健康值以及pos\n",
    "        st = []\n",
    "        for _ ,h,d,x in sorted(zip(positions, healths, directions, range(n))):\n",
    "            if d == 'R':\n",
    "                st.append([h,x])\n",
    "            else:\n",
    "                while st and h > st[-1][0]:\n",
    "                    h -= 1\n",
    "                    st.pop()\n",
    "                if st and h == st[-1][0]:\n",
    "                    st.pop()\n",
    "                elif st:\n",
    "                    st[-1][0] -= 1\n",
    "                else:\n",
    "                    hs[x] = h\n",
    "        while st:\n",
    "            h,x = st.pop()\n",
    "            hs[x] = h\n",
    "        res = [h for h in hs if h]\n",
    "        return res\n",
    "        \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        ps = sorted([(i, p) for i, p in enumerate(positions)], key=lambda x:x[1])\n",
    "        st = deque()\n",
    "        res = []\n",
    "        for i, p in ps:\n",
    "            if directions[i] == 'L':\n",
    "                while st:\n",
    "                    j = st.pop()\n",
    "                    if healths[j] > healths[i]:\n",
    "                        healths[j] -= 1\n",
    "                        st.append(j)\n",
    "                        break\n",
    "                    elif healths[j] < healths[i]:\n",
    "                        healths[i] -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    res.append(i)\n",
    "            else:\n",
    "                st.append(i)\n",
    "        \n",
    "        res = sorted([(i, healths[i]) for i in res + list(st)])\n",
    "        return [h for i, h in res] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        stack = []\n",
    "\n",
    "        h = []\n",
    "        n = len(directions)\n",
    "        for i in range(n):\n",
    "            h.append((positions[i], i, healths[i], directions[i]))\n",
    "        h.sort()\n",
    "\n",
    "        n = len(positions)\n",
    "\n",
    "        index = 0\n",
    "        while index < n:\n",
    "            heal = h[index][2]\n",
    "            direc = h[index][3]\n",
    "            robot_index = h[index][1]\n",
    "            if direc == \"R\":\n",
    "                stack.append((heal, direc, robot_index))\n",
    "            else:\n",
    "                if not stack:\n",
    "                    stack.append((heal, direc, robot_index))\n",
    "                else:\n",
    "                    dead = False\n",
    "                    while stack and stack[-1][1] == \"R\":\n",
    "                        last_h, last_d, last_robot_index = stack.pop()\n",
    "                        if last_h == heal:\n",
    "                            dead = True\n",
    "                            break\n",
    "                        elif last_h > heal:\n",
    "                            dead = True\n",
    "                            stack.append((last_h-1, \"R\", last_robot_index))\n",
    "                            break\n",
    "                        else:\n",
    "                            heal -= 1\n",
    "                    if not dead:\n",
    "                        stack.append((heal, \"L\", robot_index))\n",
    "            index += 1\n",
    "\n",
    "            # print(stack)\n",
    "\n",
    "        stack.sort(key=lambda k: k[2])\n",
    "\n",
    "        return [k[0] for k in stack]\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], dir: str) -> List[int]:\n",
    "        directions = list(dir)\n",
    "        n = len(directions)\n",
    "        dix = [i for i in range(n)]\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for _,h,d,x in sorted(zip(positions, healths, directions, dix)):\n",
    "            if d == 'R':\n",
    "                st.append([h,x])\n",
    "            else:\n",
    "                while st and h > st[-1][0]:\n",
    "                    h -= 1\n",
    "                    st.pop()\n",
    "                if st and h == st[-1][0]:\n",
    "                    st.pop()\n",
    "                elif st:\n",
    "                    st[-1][0] -= 1\n",
    "                else:\n",
    "                    ans[x] = h\n",
    "        while st:\n",
    "            h,x = st.pop()\n",
    "            ans[x] = h\n",
    "        res = [h for h in ans if h]\n",
    "        return res\n",
    "        \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(positions)\n",
    "        stk = []\n",
    "        for p, h, d, i in sorted(zip(positions, healths, directions, range(n))):\n",
    "            if d == 'L':\n",
    "                while stk:\n",
    "                    c, idx = stk.pop()\n",
    "                    if c > h:\n",
    "                        stk.append((c - 1, idx))\n",
    "                        h = 0\n",
    "                        break\n",
    "                    elif c == h:\n",
    "                        h = 0\n",
    "                        break\n",
    "                    else:\n",
    "                        h -= 1\n",
    "                if h:\n",
    "                    ans.append((h, i))\n",
    "            else:\n",
    "                stk.append((h, i))\n",
    "        if stk:\n",
    "            ans.extend(stk)\n",
    "        return [h for h, _ in sorted(ans, key=lambda x:x[1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        mach = [[positions[i],healths[i],directions[i]] for i in range(n)]\n",
    "        def K(x):\n",
    "            return x[0]\n",
    "        mach.sort(key=K)\n",
    "        print(mach)\n",
    "        q = deque([])\n",
    "        for i in range(n):\n",
    "            if not q:\n",
    "                q.append(mach[i])\n",
    "            else:\n",
    "                f = 0\n",
    "                while q:\n",
    "                    v = q.pop()\n",
    "                    if v[2] == mach[i][2] or ( v[2] == 'L' and mach[i][2] == 'R'):\n",
    "                        q.append(v)\n",
    "                        q.append(mach[i])\n",
    "                        f = 1\n",
    "                        break\n",
    "                    if v[1] > mach[i][1]:\n",
    "                        v[1] -= 1\n",
    "                        mach[i][1] = -1\n",
    "                        q.append(v)\n",
    "                        break\n",
    "                    elif v[1] < mach[i][1]:\n",
    "                        mach[i][1]-=1\n",
    "                    else:\n",
    "                        mach[i][1] = 0\n",
    "                        break\n",
    "                if mach[i][1] > 0 and f == 0:\n",
    "                    q.append(mach[i])\n",
    "        ans = []\n",
    "        dic={}\n",
    "        for v in q:\n",
    "            dic[v[0]] = v[1]\n",
    "        for p in positions:\n",
    "            if p in dic:\n",
    "                ans.append(dic[p])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        # 按照 positions 对机器人排序\n",
    "        a = sorted(zip(range(n), positions, healths, directions), key=lambda p: p[1])\n",
    "        \n",
    "        to_left = []  # 向左的机器人\n",
    "        st = []  # 向右的机器人（栈）\n",
    "        \n",
    "        for i, _, h, d in a:\n",
    "            if d == 'R':  # 向右，加入栈\n",
    "                st.append([i, h])\n",
    "                continue\n",
    "                \n",
    "            # 向左，与栈中的机器人进行碰撞处理\n",
    "            while st:\n",
    "                top = st[-1]\n",
    "                if top[1] > h:\n",
    "                    top[1] -= 1\n",
    "                    break\n",
    "                if top[1] == h:\n",
    "                    st.pop()\n",
    "                    break\n",
    "                h -= 1\n",
    "                st.pop()\n",
    "                \n",
    "            else:  # 没有 break，说明撞掉了栈中所有机器人\n",
    "                to_left.append([i, h])\n",
    "        \n",
    "        # 合并剩下的机器人\n",
    "        to_left += st\n",
    "        # 按编号排序\n",
    "        to_left.sort(key=lambda p: p[0])\n",
    "        \n",
    "        return [h for _, h in to_left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        \n",
    "        n=len(positions)\n",
    "        tmp=sorted(zip(range(n),positions,healths,directions),key=lambda x:x[1])\n",
    "        to_left=[]\n",
    "        st_to_right=[]\n",
    "        for idx,_,h,d in tmp:\n",
    "            if d=='R':\n",
    "                st_to_right.append([idx,h])\n",
    "                continue\n",
    "            while st_to_right:\n",
    "                top=st_to_right[-1]\n",
    "                if top[1]>h:\n",
    "                    top[1]-=1\n",
    "                    break\n",
    "                if top[1]==h:\n",
    "                    st_to_right.pop()\n",
    "                    break\n",
    "                h-=1\n",
    "                st_to_right.pop()\n",
    "            else:\n",
    "                to_left.append([idx,h])\n",
    "        to_left+=st_to_right\n",
    "        to_left.sort()\n",
    "        return [h for _,h in to_left]\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        a = sorted(zip(range(n), positions, healths, directions), key=lambda p: p[1])\n",
    "        to_left = []\n",
    "        st = []\n",
    "        for i, _, h, d in a:\n",
    "            if d == 'R':  # 向右，存入栈中\n",
    "                st.append([i, h])\n",
    "                continue\n",
    "            # 当前机器人向左，与栈中向右的机器人碰撞\n",
    "            while st:\n",
    "                top = st[-1]\n",
    "                if top[1] > h:  # 栈顶的健康度大\n",
    "                    top[1] -= 1\n",
    "                    break\n",
    "                if top[1] == h:  # 健康度一样大\n",
    "                    st.pop()\n",
    "                    break\n",
    "                h -= 1  # 当前机器人的健康度大\n",
    "                st.pop()  # 移除栈顶\n",
    "            else:  # while 循环没有 break，说明当前机器人把栈中的全部撞掉\n",
    "                to_left.append([i, h])\n",
    "        to_left += st  # 合并剩余的机器人\n",
    "        to_left.sort(key=lambda p: p[0])  # 按编号排序\n",
    "        return [h for _, h in to_left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        a = sorted(zip(range(n), positions, healths, directions), key=lambda p: p[1])\n",
    "        to_left = []\n",
    "        st = []\n",
    "        for i, _, h, d in a:\n",
    "            if d == 'R':\n",
    "                st.append([i, h])\n",
    "                continue\n",
    "            while st:\n",
    "                top = st[-1]\n",
    "                if top[1] > h:\n",
    "                    top[1] -= 1\n",
    "                    break\n",
    "                if top[1] == h:\n",
    "                    st.pop()\n",
    "                    break\n",
    "                h -= 1\n",
    "                st.pop()\n",
    "            else:\n",
    "                to_left.append([i, h])\n",
    "        to_left += st\n",
    "        to_left.sort(key=lambda p: p[0])\n",
    "        return [h for _, h in to_left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        a = sorted(zip(range(n), positions, healths, directions), key=lambda p: p[1])\n",
    "        to_left = []\n",
    "        st = []\n",
    "        for i, _, h, d in a:\n",
    "            if d == 'R':  # 向右，存入栈中\n",
    "                st.append([i, h])\n",
    "                continue\n",
    "            # 当前机器人向左，与栈中向右的机器人碰撞\n",
    "            while st:\n",
    "                top = st[-1]\n",
    "                if top[1] > h:  # 栈顶的健康度大\n",
    "                    top[1] -= 1\n",
    "                    break\n",
    "                if top[1] == h:  # 健康度一样大\n",
    "                    st.pop()\n",
    "                    break\n",
    "                h -= 1  # 当前机器人的健康度大\n",
    "                st.pop()  # 移除栈顶\n",
    "            else:  # while 循环没有 break，说明当前机器人把栈中的全部撞掉\n",
    "                to_left.append([i, h])\n",
    "        to_left += st  # 合并剩余的机器人\n",
    "        to_left.sort(key=lambda p: p[0])  # 按编号排序\n",
    "        return [h for _, h in to_left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        a = sorted(zip(range(n), positions, healths, directions), key=lambda p: p[1])\n",
    "        to_left = []\n",
    "        st = []\n",
    "        for i, _, h, d in a:\n",
    "            if d == 'R':\n",
    "                st.append([i, h])\n",
    "                continue\n",
    "            while st:\n",
    "                top = st[-1]\n",
    "                if top[1] > h:\n",
    "                    top[1] -= 1\n",
    "                    break\n",
    "                if top[1] == h:\n",
    "                    st.pop()\n",
    "                    break\n",
    "                h -= 1\n",
    "                st.pop()\n",
    "            else:\n",
    "                to_left.append([i, h])\n",
    "        to_left += st\n",
    "        to_left.sort(key=lambda p: p[0])\n",
    "        return [h for _, h in to_left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        stack = []\n",
    "        remain = []\n",
    "        for idx, p, h, d in sorted(zip(range(n), positions, healths, directions), key = lambda x: x[1]):\n",
    "            if d == 'R':\n",
    "                stack.append([idx, h])\n",
    "            else:\n",
    "                while stack:\n",
    "                    if stack[-1][1] < h:\n",
    "                        stack.pop()\n",
    "                        h -= 1 \n",
    "                    elif stack[-1][1] == h:\n",
    "                        stack.pop()\n",
    "                        break \n",
    "                    else:\n",
    "                        stack[-1][1] -= 1 \n",
    "                        break \n",
    "                else:\n",
    "                    remain.append([idx, h])\n",
    "        remain += stack\n",
    "        remain.sort()\n",
    "        return [h for idx, h in remain]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n=len(positions)\n",
    "        arr=sorted(zip(range(n),positions,healths,directions),key=lambda p:p[1])\n",
    "        stack=[]\n",
    "        left=[]\n",
    "       \n",
    "        for i,_,h,d in arr:\n",
    "            if d=='R':\n",
    "                stack.append([i,h])\n",
    "                continue\n",
    "            while stack:\n",
    "                top=stack[-1]\n",
    "                if top[1]>h:\n",
    "                    top[1] -=1\n",
    "                    break\n",
    "                elif top[1]==h:\n",
    "                    stack.pop()\n",
    "                    break\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    h -=1\n",
    "            else:\n",
    "                left.append([i,h])\n",
    "\n",
    "        left +=stack\n",
    "        left.sort(key=lambda p:p[0])\n",
    "       \n",
    "        return [x for _,x in left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        a = sorted(zip(range(n), positions, healths, directions), key=lambda p: p[1])\n",
    "        to_left = []\n",
    "        st = []\n",
    "        for i, _, h, d in a:\n",
    "            if d == 'R':\n",
    "                st.append([i, h])\n",
    "                continue\n",
    "            while st:\n",
    "                top = st[-1]\n",
    "                if top[1] > h:\n",
    "                    top[1] -= 1\n",
    "                    break\n",
    "                if top[1] == h:\n",
    "                    st.pop()\n",
    "                    break\n",
    "                h -= 1\n",
    "                st.pop()\n",
    "            else:\n",
    "                to_left.append([i, h])\n",
    "        to_left += st\n",
    "        to_left.sort(key=lambda p: p[0])\n",
    "        return [h for _, h in to_left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        stack = []\n",
    "        remain = []\n",
    "        for idx, p, h, d in sorted(zip(range(n), positions, healths, directions), key = lambda x: x[1]):\n",
    "            if d == 'R':\n",
    "                stack.append([idx, h])\n",
    "            else:\n",
    "                while stack:\n",
    "                    if stack[-1][1] < h:\n",
    "                        stack.pop()\n",
    "                        h -= 1\n",
    "                    elif stack[-1][1] == h:\n",
    "                        stack.pop() \n",
    "                        break  \n",
    "                    else:\n",
    "                        stack[-1][1] -= 1\n",
    "                        break \n",
    "                else:\n",
    "                    remain.append([idx, h])\n",
    "        remain += stack\n",
    "        remain.sort()\n",
    "        return [h for i, h in remain]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        robots = sorted((p, i, h, d) for i, (p, h, d) in enumerate(zip(positions, healths, directions)))\n",
    "        right_stack = []\n",
    "        result = []\n",
    "        for p, i, h, d in robots:\n",
    "            if d == 'R':\n",
    "                right_stack.append([i, h])\n",
    "            else:\n",
    "                while right_stack:\n",
    "                    if right_stack[-1][1] <= h:\n",
    "                        _, h2 = right_stack.pop()\n",
    "                        if h2 == h:\n",
    "                            break\n",
    "                        else:\n",
    "                            h -= 1\n",
    "                    else:\n",
    "                        right_stack[-1][1] -= 1\n",
    "                        break\n",
    "                else:\n",
    "                    result.append([i, h])\n",
    "        result.extend(right_stack)\n",
    "        result.sort()\n",
    "        return [h for _, h in result]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        a = sorted(zip(range(n), positions, healths, directions), key=lambda p: p[1])\n",
    "        to_left = []\n",
    "        st = []\n",
    "        for i, _, h, d in a:\n",
    "            if d == 'R':  # 向右，存入栈中\n",
    "                st.append([i, h])\n",
    "                continue\n",
    "            # 当前机器人向左，与栈中向右的机器人碰撞\n",
    "            while st:\n",
    "                top = st[-1]\n",
    "                if top[1] > h:  # 栈顶的健康度大\n",
    "                    top[1] -= 1\n",
    "                    break\n",
    "                if top[1] == h:  # 健康度一样大\n",
    "                    st.pop()\n",
    "                    break\n",
    "                h -= 1  # 当前机器人的健康度大\n",
    "                st.pop()  # 移除栈顶\n",
    "            else:  # while 循环没有 break，说明当前机器人把栈中的全部撞掉\n",
    "                to_left.append([i, h])\n",
    "        to_left += st  # 合并剩余的机器人\n",
    "        to_left.sort(key=lambda p: p[0])  # 按编号排序\n",
    "        return [h for _, h in to_left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        a = sorted(zip(range(n), positions, healths, directions), key=lambda p: p[1])\n",
    "        to_left = []\n",
    "        st = []\n",
    "        for i, _, h, d in a:\n",
    "            if d == 'R':  # 向右，存入栈中\n",
    "                st.append([i, h])\n",
    "                continue\n",
    "            # 当前机器人向左，与栈中向右的机器人碰撞\n",
    "            while st:\n",
    "                top = st[-1]\n",
    "                if top[1] > h:  # 栈顶的健康度大\n",
    "                    top[1] -= 1\n",
    "                    break\n",
    "                if top[1] == h:  # 健康度一样大\n",
    "                    st.pop()\n",
    "                    break\n",
    "                h -= 1  # 当前机器人的健康度大\n",
    "                st.pop()  # 移除栈顶\n",
    "            else:  # while 循环没有 break，说明当前机器人把栈中的全部撞掉\n",
    "                to_left.append([i, h])\n",
    "        to_left += st  # 合并剩余的机器人\n",
    "        to_left.sort(key=lambda p: p[0])  # 按编号排序\n",
    "        return [h for _, h in to_left]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        stack = []\n",
    "        remain = []\n",
    "        for idx, p, h, d in sorted(zip(range(n), positions, healths, directions), key = lambda x: x[1]):\n",
    "            if d == 'R':\n",
    "                stack.append([idx, h])\n",
    "            else:\n",
    "                while stack:\n",
    "                    if stack[-1][1] < h:\n",
    "                        stack.pop()\n",
    "                        h -= 1 \n",
    "                    elif stack[-1][1] == h:\n",
    "                        stack.pop()\n",
    "                        break \n",
    "                    else:\n",
    "                        stack[-1][1] -= 1 \n",
    "                        break \n",
    "                else:\n",
    "                    remain.append([idx, h])\n",
    "        remain += stack\n",
    "        remain.sort()\n",
    "        return [h for idx, h in remain]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        l=len(positions)\n",
    "        ls=[]\n",
    "        for i in range(l):\n",
    "            ls.append([positions[i],healths[i],directions[i],i])\n",
    "        ls.sort()\n",
    "        ret=[]\n",
    "        q=[]\n",
    "        for i in range(l):\n",
    "            p,h,d,num=ls[i]\n",
    "            if d==\"L\":\n",
    "                while q:\n",
    "                    number,tp=q.pop()\n",
    "                    if tp>h:\n",
    "                        q.append((number,tp-1))\n",
    "                        h=0\n",
    "                        break\n",
    "                    elif tp==h:\n",
    "                        h=0\n",
    "                        break\n",
    "                    else:\n",
    "                        h-=1\n",
    "                if h!=0:\n",
    "                    ret.append((num,h))\n",
    "            if d==\"R\":\n",
    "                q.append((num,h))\n",
    "        ret+=q\n",
    "        ret.sort()\n",
    "        ans=[]\n",
    "        for a,b in ret:\n",
    "            ans.append(b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def survivedRobotsHealths(self, positions, healths, directions):\n",
    "        \"\"\"\n",
    "        :type positions: List[int]\n",
    "        :type healths: List[int]\n",
    "        :type directions: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        T=list()\n",
    "        p,h,d=positions,healths,directions\n",
    "        N=len(positions)\n",
    "        for i in range(N):\n",
    "            T.append([p[i],h[i],d[i],i])\n",
    "        del p,h,d\n",
    "        T.sort(key=lambda x : x[0])\n",
    "        A=list()\n",
    "        ans=list()\n",
    "        for i in range(N):\n",
    "            if T[i][2]=='R':\n",
    "                A.append([T[i][1],T[i][3]])\n",
    "            else:\n",
    "                while len(A)>0 and T[i][1]>0:\n",
    "                    if A[-1][0]>T[i][1]:\n",
    "                        A[-1][0]-=1\n",
    "                        T[i][1]=0\n",
    "                    elif A[-1][0]<T[i][1]:\n",
    "                        A.pop()\n",
    "                        T[i][1]-=1\n",
    "                    else:\n",
    "                        A.pop()\n",
    "                        T[i][1]=0\n",
    "                if len(A)==0 and T[i][1]>0:\n",
    "                    ans.append((T[i][1],T[i][3]))\n",
    "        ans.extend(A)\n",
    "        ans.sort(key=lambda x:x[1])\n",
    "        for i in range(len(ans)):\n",
    "            ans[i]=ans[i][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        stack = []\n",
    "        remain = []\n",
    "        for idx, p, h, d in sorted(zip(range(n), positions, healths, directions), key = lambda x: x[1]):\n",
    "            if d == 'R':\n",
    "                stack.append([idx, h])\n",
    "            else:\n",
    "                while stack:\n",
    "                    if stack[-1][1] < h:\n",
    "                        stack.pop()\n",
    "                        h -= 1\n",
    "                    elif stack[-1][1] == h:\n",
    "                        stack.pop() \n",
    "                        break  \n",
    "                    else:\n",
    "                        stack[-1][1] -= 1\n",
    "                        break \n",
    "                else:\n",
    "                    remain.append([idx, h])\n",
    "        remain += stack\n",
    "        remain.sort()\n",
    "        return [h for i, h in remain]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        a = sorted(zip(range(n), positions, healths, directions), key=lambda x: x[1])\n",
    "        to_left=[]\n",
    "        st=[]\n",
    "        for i,_,h,d in a :\n",
    "            if d=='R' :\n",
    "                st.append([i,h])\n",
    "                continue\n",
    "            while st :\n",
    "                top=st[-1]\n",
    "                if top[1]>h :\n",
    "                    top[1]-=1\n",
    "                    break\n",
    "                if top[1]==h :\n",
    "                    st.pop()\n",
    "                    break\n",
    "                h-=1\n",
    "                st.pop()\n",
    "            else :\n",
    "                to_left.append([i,h])\n",
    "        to_left+=st\n",
    "        to_left.sort(key=lambda x: x[0])\n",
    "        return [h for _,h in to_left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        robots = []\n",
    "        n = len(positions)\n",
    "        for i in range(n):\n",
    "            robots.append((i, positions[i], healths[i], directions[i]))\n",
    "        \n",
    "        robots.sort(key=lambda x: x[1])\n",
    "        \n",
    "        res = []\n",
    "        r = []\n",
    "        for i, p, h, d in robots:\n",
    "            if not r:\n",
    "                if d == 'R':\n",
    "                    r.append([i, h])\n",
    "                else:\n",
    "                    res.append([i, h])\n",
    "            else:\n",
    "                if d == 'L':\n",
    "                    while r and h > 0:\n",
    "                        if r[-1][1] > h:\n",
    "                            r[-1][1] -= 1\n",
    "                            h = 0\n",
    "                        elif r[-1][1] == h:\n",
    "                            r.pop(-1)\n",
    "                            h = 0\n",
    "                        else:\n",
    "                            h -= 1\n",
    "                            r.pop(-1)\n",
    "                    if h > 0:\n",
    "                        res.append([i, h])\n",
    "                            \n",
    "                else:\n",
    "                    r.append([i, h])\n",
    "        return ([i[1] for i in sorted(res + r)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        zipList = sorted(zip([i for i in range(n)],positions,healths,directions),key = lambda x:x[1])\n",
    "        res = []\n",
    "        rightToLeft = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            index,p,h,d = zipList[i]\n",
    "            if d == 'L':\n",
    "                rightToLeft.append(h)\n",
    "            else:\n",
    "                curHealth = h\n",
    "                while rightToLeft:\n",
    "                    if curHealth>rightToLeft[-1]:\n",
    "                        rightToLeft.pop()\n",
    "                        curHealth-=1\n",
    "                    elif curHealth<rightToLeft[-1]:\n",
    "                        rightToLeft[-1]-=1\n",
    "                        curHealth=0\n",
    "                        break\n",
    "                    else:\n",
    "                        rightToLeft.pop()\n",
    "                        curHealth=0\n",
    "                        break\n",
    "                        \n",
    "                if curHealth>0:\n",
    "                    res.append((index,curHealth))\n",
    "                        \n",
    "        leftToRight = []\n",
    "        \n",
    "        for i in range(n):\n",
    "            index,p,h,d = zipList[i]\n",
    "            \n",
    "            if d == 'R':\n",
    "                leftToRight.append(h)\n",
    "                \n",
    "            else:\n",
    "                curHealth = h\n",
    "                while leftToRight:\n",
    "                    if curHealth>leftToRight[-1]:\n",
    "                        leftToRight.pop()\n",
    "                        curHealth-=1\n",
    "                    elif curHealth<leftToRight[-1]:\n",
    "                        leftToRight[-1]-=1\n",
    "                        curHealth=0\n",
    "                        break\n",
    "                    else:\n",
    "                        leftToRight.pop()\n",
    "                        curHealth=0\n",
    "                        break\n",
    "                \n",
    "                if curHealth>0:\n",
    "                    res.append((index,curHealth))\n",
    "        res.sort()\n",
    "        print(res)\n",
    "        ans = []\n",
    "        for r in res:\n",
    "            ans.append(r[1])\n",
    "        return ans\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        rb = [(p, h, d, i) for p, h, d, i in zip(positions, healths, directions, range(len(positions)))]\n",
    "        rb.sort()\n",
    "        st = []\n",
    "        for p, h, d, i in rb:\n",
    "            while st and d == 'L' and st[-1][2] == 'R':\n",
    "                if h > st[-1][1]:\n",
    "                    st.pop()\n",
    "                    h -= 1\n",
    "                    continue\n",
    "                elif h == st[-1][1]:\n",
    "                    st.pop()\n",
    "                else:\n",
    "                    st[-1][1] -= 1\n",
    "                break\n",
    "            else:\n",
    "                if h > 0:\n",
    "                    st.append([p, h, d, i])\n",
    "        st.sort(key=lambda x:x[3])\n",
    "        return [h for p, h, d, i in st if h > 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        ps=[[e,i] for i,e in enumerate(positions)]\n",
    "        ps.sort()\n",
    "       # print(ps)\n",
    "        q=[]#[0,h]\n",
    "        for e,i in ps:\n",
    "            if directions[i]=='R':\n",
    "                q.append([i,directions[i],healths[i]])\n",
    "                continue\n",
    "            if q and q[-1][1]!=directions[i]:\n",
    "                while q and q[-1][1]!=directions[i] and q[-1][2]<healths[i]:\n",
    "                    healths[i]-=1\n",
    "                    q.pop()\n",
    "                \n",
    "            if not q or q[-1][1]==directions[i]:\n",
    "                q.append([i,directions[i],healths[i]])\n",
    "            elif q[-1][2]==healths[i]:\n",
    "                q.pop()  \n",
    "            else:\n",
    "                q[-1][2]-=1\n",
    "        q.sort()   \n",
    "        return [h for i,r,h in q]\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n=len(positions)\n",
    "        ind=[_ for _ in range(n)]\n",
    "        to_left=[];st=[]\n",
    "        a=sorted(zip(ind,positions,healths,directions),key=lambda p:p[1])\n",
    "        for i,p,h,d in a:\n",
    "            if d==\"R\": \n",
    "                st.append([i,h])\n",
    "                continue\n",
    "            while st:\n",
    "                if st[-1][1]==h:\n",
    "                    st.pop(-1)\n",
    "                    break\n",
    "                elif st[-1][1]>h:\n",
    "                    st[-1][1]-=1\n",
    "                    break\n",
    "                st.pop(-1)\n",
    "                h-=1\n",
    "            else:\n",
    "                to_left.append([i,h])\n",
    "        res=sorted(to_left+st,key=lambda x:x[0])\n",
    "        ans=[i for _,i in res]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        ans = []\n",
    "        s = []  # [health]\n",
    "        for _, h, d, i in sorted([[p, h, d, i] for i, (p, h, d) in enumerate(zip(positions, healths, directions))]):\n",
    "            if d == 'L':\n",
    "                while s and h:\n",
    "                    lst = s.pop()\n",
    "                    if lst[1] < h:\n",
    "                        h -= 1  # type: ignore\n",
    "                    elif lst[1] == h:\n",
    "                        h = 0\n",
    "                    else:\n",
    "                        h = 0\n",
    "                        if lst[1] > 0:\n",
    "                            s.append([lst[0], lst[1] - 1])\n",
    "\n",
    "                if h:\n",
    "                    ans.append([i, h])\n",
    "            else:\n",
    "                s.append([i, h])\n",
    "        return [v for _, v in sorted(ans + s)]  # type: ignore\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        arr = sorted(list(zip(positions, healths, directions, range(n))))\n",
    "        s = []\n",
    "        for pos, heal, dire, idx in arr:\n",
    "            flag = True\n",
    "            while s and s[-1][1] == \"R\" and dire == \"L\":\n",
    "                if s[-1][0] == heal:\n",
    "                    flag = False\n",
    "                    s.pop()\n",
    "                    break\n",
    "                elif s[-1][0] > heal:\n",
    "                    flag = False\n",
    "                    s[-1][0] -= 1\n",
    "                    break\n",
    "                else:\n",
    "                    s.pop()\n",
    "                    heal -= 1\n",
    "            if flag:\n",
    "                s.append([heal, dire, idx])\n",
    "        return [e[0] for e in sorted(s, key=lambda x: x[-1])]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        stk = deque()\n",
    "        phds = []\n",
    "        for i, (p, h, d) in enumerate(zip(positions, healths, list(directions))):\n",
    "            phds.append([p, h, d, i])\n",
    "        phds.sort()\n",
    "        ans = []\n",
    "        for p, h, d, i in phds:\n",
    "            if d == 'L':\n",
    "                is_die = False\n",
    "                while stk:\n",
    "                    if stk[-1][0] > h:\n",
    "                        stk[-1][0] -= 1\n",
    "                        is_die = True\n",
    "                        break\n",
    "                    elif stk[-1][0] == h:\n",
    "                        stk.pop()\n",
    "                        is_die = True\n",
    "                        break\n",
    "                    else:\n",
    "                        stk.pop()\n",
    "                        h -= 1\n",
    "                if not is_die:\n",
    "                    ans.append([h, i])\n",
    "            else:\n",
    "                stk.append([h, i])\n",
    "        ans = ans + list(stk)\n",
    "        ans.sort(key=lambda x: x[1])\n",
    "        rst = [x[0] for x in ans]\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:        \n",
    "        n=len(positions)\n",
    "        robot=list(zip(range(n), positions,healths,list(directions)))\n",
    "        robot.sort(key=lambda x:x[1])\n",
    "        res=list()\n",
    "        # return robot\n",
    "        for i,p,h,d in robot:\n",
    "            if d==\"R\":\n",
    "                res.append([i,p,h,d])\n",
    "                continue\n",
    "\n",
    "            while res and d==\"L\" and res[-1][-1]==\"R\" and h>0 and res[-1][2]<=h:\n",
    "                if res[-1][2]==h:\n",
    "                    res.pop()\n",
    "                    h=0\n",
    "                    break \n",
    "                res.pop()\n",
    "                h-=1\n",
    "            if h>0:\n",
    "                if res and res[-1][-1]==\"R\" and res[-1][2]>h:\n",
    "                    res[-1][2]-=1\n",
    "                else:\n",
    "\n",
    "                    res.append([i,p,h,d])\n",
    "        return [h for _,_,h,_ in sorted(res)]\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        arr = []\n",
    "        for i, (p, h, d) in enumerate(zip(positions, healths, directions)):\n",
    "            arr.append([p, h, d, i])\n",
    "        arr.sort()\n",
    "        stack = []\n",
    "        for p, h, d, i in arr:\n",
    "            while stack:\n",
    "                if stack[-1][2] == 'R' and d == 'L':\n",
    "                    if stack[-1][1] == h:\n",
    "                        h = 0\n",
    "                        stack.pop()\n",
    "                        break\n",
    "                    elif stack[-1][1] < h:\n",
    "                        h -= 1\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        stack[-1][1] -= 1\n",
    "                        h = 0\n",
    "                        break\n",
    "                else: break\n",
    "            if h:\n",
    "                stack.append([p, h, d, i])\n",
    "        \n",
    "        stack.sort(key=lambda x: x[3])\n",
    "        \n",
    "        return [x[1] for x in stack]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n = len(positions)\n",
    "        robots = list(zip(range(n), positions, healths, directions))\n",
    "        robots.sort(key=lambda x: x[1])\n",
    "        robots = [list(robot) for robot in robots]\n",
    "        \n",
    "        stack = deque()\n",
    "        alives = []\n",
    "        for robot in robots:\n",
    "            if robot[3] == 'R':\n",
    "                stack.append(robot)\n",
    "            else:\n",
    "                while stack and stack[-1][2] < robot[2]:\n",
    "                    stack.pop()\n",
    "                    robot[2] -= 1\n",
    "                if stack:\n",
    "                    if stack[-1][2] == robot[2]:\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        stack[-1][2] -= 1\n",
    "                else:\n",
    "                    alives.append(robot)\n",
    "        while stack:\n",
    "            alives.append(stack.pop())\n",
    "        alives.sort()\n",
    "        return [robot[2] for robot in alives]\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:\n",
    "        n=len(positions)\n",
    "        s={}\n",
    "        for i in range(n):\n",
    "            s[positions[i]]=i\n",
    "        ro=[[positions[i],healths[i],directions[i]] for i in range(n)]\n",
    "        ro.sort()\n",
    "        stack=[]\n",
    "        for one in ro:\n",
    "            stack.append(one)\n",
    "            while len(stack)>1 and stack[-2][2]=='R' and stack[-1][2]=='L':\n",
    "                now=stack.pop()\n",
    "                last=stack.pop()\n",
    "                if last[1]>now[1]:\n",
    "                    last[1]-=1\n",
    "                    stack.append(last)\n",
    "                elif last[1]<now[1]:\n",
    "                    now[1]-=1\n",
    "                    stack.append(now)\n",
    "            # print(stack)\n",
    "        stack.sort(key=lambda i:s[i[0]])\n",
    "        return [i[1] for i in stack]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
